package main

import "fmt"

/**
 * @param s: A string
 * @param t: A string
 * @return: Count the number of distinct subsequences
 */
func NumDistinct(s string, t string) int {
	n := len(s)
	m := len(t)
	if n > 0 && m == 0 {
		return 1
	}
	if n == 0 || m == 0 || n < m {
		return 0
	}

	cache := make([][]int, n)
	for i := 0; i < n; i++ {
		cache[i] = make([]int, m)
		for j := 0; j < m; j++ {
			cache[i][j] = -1
		}
	}

	ans := dfs(s, t, n-1, m-1, cache)
	if ans < 0 {
		ans = 0
	}

	return ans
}

func dfs(s, t string, i, j int, cache [][]int) int {
	if cache[i][j] != -1 {
		return cache[i][j]
	}

	ans := -1
	if i == 0 && j == 0 {
		ans = 0
		if s[i] == t[j] {
			ans = 1
		}
	} else if j == 0 {
		if s[i] == t[j] {
			ans = dfs(s, t, i-1, j, cache) + 1
		} else {
			ans = dfs(s, t, i-1, j, cache)
		}
	} else if i == 0 { //和第77题目 最长公共子序列的区别1
		ans = 0
	} else {
		//普遍位置怎么求
		ans = dfs(s, t, i-1, j, cache)

		//和第77题目 最长公共子序列的区别1
		if s[i] == t[j] {
			ans += dfs(s, t, i-1, j-1, cache)
		}
	}
	cache[i][j] = ans
	return ans
}

func main() {
	fmt.Println(NumDistinct("rabbbit", "rabbit"))
	fmt.Println(NumDistinct("abcd", ""))
}
